package com.fulin.datastract.heap;

import java.io.File;
import java.util.Arrays;

import org.springframework.util.DigestUtils;

/**
*
* @description 大顶堆
* @auther fulin16@crnet.com.hk
* @since 2020年6月30日 上午10:12:56
*
*/
@SuppressWarnings("all")
public class MaxHeap<T extends Comparable<? super T>> {
	private int size; //堆的大小
	private int length;
	private T[] data; //数组,用于实现堆，堆就是一个完全二叉树,所以非常适合用数组存储
	
	public MaxHeap(int size) {
		this.size = size;
		data = (T[])new Comparable[size];
		this.length = 0;
	}
	
	public void add(T t) {
		if(length == size ) {
			return;
		}
		
		//根节点
		if(length == 0) {
			data[0] = t;
			length ++;
			return;
		}
		
		data[length] = t;
		length ++;
		//自下而上的更新堆
		int childIndex = length - 1;
		int fatherIndex = (childIndex - 1) >> 1;
		while(data[fatherIndex].compareTo(data[childIndex]) < 0) {
			swap(data,childIndex,fatherIndex);
			if(fatherIndex == 0) {
				break;
			}
			childIndex = fatherIndex;
			fatherIndex = (fatherIndex -1 ) >> 1;
		}
	}
	
	
	public void remove() {
		
	}
	
	
	private void swap(T[] arr, int childIndex, int fatherIndex) {
		T temp = arr[childIndex]; 
		data[childIndex] = data[fatherIndex];
		data[fatherIndex] = temp;
	}

	/**
	 * 堆化
	 */
	public void heapify() {
		
	}
	
	public void printHeap() {
		for (int i = 0; i < data.length; i++) {
			T t = data[i];
			if(i == 0 || i == 2 || i == 6 || i == 14) {
				//当前层的最后一个节点
				System.out.println(t);
			}else {
				System.out.print(t + "\t");
			}
		}
		
		System.out.println("\n" + Arrays.toString(data));
	}
	
	public static void main(String[] args) {
		int[] arr = {1,2,3,4,20,6,7,8,40,9,10,60,8,30};
		MaxHeap heap = new MaxHeap(arr.length);
		
		for (int i = 0; i < arr.length; i++) {
			heap.add(arr[i]);
		}
		
		System.out.println(Arrays.toString(arr));
		heap.printHeap();
	}
}
